package xiaohu.day7.HJ77;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.Scanner;
import java.util.Stack;
import java.util.Collections;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 获取输入火车数
        int n = in.nextInt();
        // 定义一个队列，表示需要进入的火车
        Queue<String> que = new LinkedList<>();
        // 定义一个栈，模拟火车进出站
        Stack<String> stack = new Stack<>();
        // 定义一个List集合，用于存放火车出栈顺序集合
        List<String> list = new ArrayList<>();
        // 定义一个String，表示出栈顺序
        String pop = "";
        // 将火车进入队列
        for (int i = 0; i < n; i++) {
            que.offer(String.valueOf(in.nextInt()));
        }
        // 模拟火车进出站
        trainEnter(que, stack, list, pop);
        // 对出栈顺序集合进行排序
        Collections.sort(list);
        // 输出结果
        list.forEach(p-> {
            System.out.println(p);
        });
    }

    /**
     * 模拟火车进站或出栈.
     */
    private static void trainEnter(Queue<String> que, Stack<String> stack,
                                   List<String> list, String pop) {
        //递归的中止条件
        if (que.isEmpty() && stack.isEmpty()) {
            // 进站队列和栈都为null，则return,将出栈顺序添加到list
            list.add(pop);
            return;
        }
        // 只要车站还存在车，遍出栈
        if (!stack.isEmpty()) {
            // 先克隆,保证数据的原始性质
            Queue<String> tempQueue = new LinkedList<>(que);
            Stack<String> tempStack = (Stack<String>) stack.clone();
            // 栈顶出栈
            String tempOutQueue = pop + (tempStack.pop() + " ");
            // 递归调用，下一个车辆进站
            trainEnter(tempQueue, tempStack, list, tempOutQueue);
        }
        // 主要车队不为空，遍进站
        if (!que.isEmpty()) {
            // 先克隆,保证数据的原始性质
            Queue<String> tempQueue = new LinkedList<>(que);
            Stack<String> tempStack = (Stack<String>) stack.clone();
            // 后车出队列，返回队列第一个元素，并删除
            String train = tempQueue.poll();
            // 后车进站
            tempStack.push(train);
            // 递归调用，下一个车辆进站
            trainEnter(tempQueue, tempStack, list, pop);
        }
    }
}
